#include "BTreeNode.h"

// created by me:
#include <iostream>
using namespace std;

/*
anatomy of the LEAF NODE BUFFER (1024 bytes):
	4 bytes: counter
	pageid pointer (to next leaf node): 4 bytes 
	84 * 12 bytes: tuples
	------ 8 bytes wasted
*/

void Node::insert_to_node (char init_buf[], char entry[], int key, int count) {
	if ( count == 0 ) {
		memcpy(init_buf, entry, entry_size);
		return;
	} 

	int max = count-1;
	int min = 0;
	int mid = (max + min)/2;

	int k;	// some k that already exists inside the buffer, id-ed by mid
	memcpy(&k ,init_buf + mid*entry_size, key_size);
	// BINARY SEARCH
	// dealing with odd numbers.
	if ( count%2 == 1 && count > 1)	{
		memcpy(&k ,init_buf + (mid)*entry_size, key_size);
		if ( key > k ) {
			min = mid+1; // go right
		} else if ( key < k ) {
			max = mid-1; // go left
		}
	}
	
	int offset;
	while ( max >= min ) {
		mid = (min + max)/2;
		memcpy(&k ,init_buf + (mid)*entry_size, key_size);

		if ( min == max ) {	// for count = 1, and corners
			if ( key < k ) {	// insert into the left
				for (int i = count-mid; i != 0; i--) {
					memcpy(init_buf + (mid+i)*entry_size, init_buf + (mid+i-1)*entry_size, entry_size);
				}
				offset = mid*entry_size;
				break;

			} else if ( key > k ) {	// insert into the right
				for (int i = count-mid-1; i != 0; i--) {
					memcpy(init_buf + (mid+i+1)*entry_size, init_buf + (mid+i)*entry_size, entry_size);
				}
				offset = (mid+1)*entry_size;
				break;
			}
		}

		if (k < key) { // change min index to search upper subarray
			if ( mid == count - 1)
				min = count - 1;
			else 
				min = mid + 1;
		}
		else if (k > key) { // change max index to search lower subarray
			max = mid;
		} 
	}
	//cout << "node insert function complete" << endl;
	memcpy(init_buf + offset, entry, entry_size);	// insert 
}

void Node::see_inside() {
	// for testing: print out everything in the node.
	// print out to see what is in buffer now
	int count;
	int ptr;
	char* init_buf = buffer + 2*sizeof(int);

	memcpy(&count, buffer, sizeof(int));
	memcpy(&ptr, buffer + sizeof(int), sizeof(int));


	cout << "count: " << count << endl;
	cout << "ptr: " << ptr << endl;
	
	for ( int i = 0; i < count; i++ ) {
		int key_;
		int pid_;
		//int sid_;

		memcpy(&key_, init_buf + i*entry_size, key_size);
		memcpy(&pid_, init_buf + i*entry_size + key_size, key_size);
		//memcpy(&sid_, init_buf + i*entry_size + 2*key_size, key_size);
		//cout << key_ << " " << pid_ << " " << sid_ << endl;
		cout << key_ << " " << pid_ << endl;
	} 
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int Node::getKeyCount()
{
	// this number is stored in the first 4 bytes of the buffer
	int count;
	memcpy(&count, buffer, sizeof(int));
	return count;
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC Node::read(PageId pid, const PageFile& pf)
{
	 RC rc = pf.read(pid, buffer);
	 return rc;
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC Node::write(PageId pid, PageFile& pf)
{
	RC rc = pf.write(pid, buffer); 
	return rc;
}
 
BTLeafNode::BTLeafNode()
{
	max_num_keys = 84;
	key_size = sizeof(int);
	id_size = sizeof(RecordId);
	entry_size = key_size + id_size;

	int init_count = 0;
	memcpy(&buffer, &init_count, sizeof(int));

	int init_pointer = 0;
	memcpy(&buffer + sizeof(int), &init_pointer, sizeof(int));
	getKeyCount();
}

 /*
 * Insert a (key, rid) pair to the node.
 * @param key[IN] the key to insert
 * @param rid[IN] the RecordId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTLeafNode::insert(int key, const RecordId& rid)
{
	// find where to insert
	int count = getKeyCount();
	if ( count == max_num_keys ) {
		return RC_NODE_FULL;
	}

	// set up entry (for easier insertion)
	char entry[12];
	memcpy(entry, &key, key_size);
	memcpy(entry + key_size, &rid, id_size);

	char* init_buf = buffer + 2*sizeof(int);	// take into account count and pointer
	
	insert_to_node(init_buf, entry, key, count);

	count++;
	memcpy(buffer, &count, sizeof(int));

	return 0;
}

/*
 * Insert the (key, rid) pair to the node
 * and split the node half and half with sibling.
 * The first key of the sibling node is returned in siblingKey.
 * @param key[IN] the key to insert.
 * @param rid[IN] the RecordId to insert.
 * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called.
 * @param siblingKey[OUT] the first key in the sibling node after split.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::insertAndSplit(int key, const RecordId& rid, 
                              BTLeafNode& sibling, int& siblingKey)
{ 
	// create a temp buffer
	char temp_buf[1024];	// holds 85 tuples + 4 bytes
	int count = getKeyCount();
	memcpy(temp_buf, buffer + 2*sizeof(int), entry_size*count);

	char entry[12];
	memcpy(entry, &key, key_size);
	memcpy(entry + key_size, &rid, id_size);

	insert_to_node(temp_buf, entry, key, count);

	count++;	// should be +1

	int mid = count/2;	// if odd, the second node will get one more entry
	// original node:
	memcpy(buffer + 2*sizeof(int), temp_buf, entry_size*mid);
	memcpy(buffer, &mid, sizeof(int));	// resetting count

	// new node:
	memcpy(sibling.buffer + 2*sizeof(int), temp_buf + entry_size*mid, entry_size*(count-mid));
	int new_count = count-mid;
	memcpy(sibling.buffer, &new_count, sizeof(int));	// setting count
	memcpy(&siblingKey, sibling.buffer + 2*sizeof(int), key_size);
	return 0; 
}

/*
 * Find the FIRST entry whose key value is larger than or equal to searchKey
 * and output the eid (entry number) whose key value >= searchKey.
 * Remeber that all keys inside a B+tree node should be kept sorted.
 * @param searchKey[IN] the key to search for
 * @param eid[OUT] the entry number that contains a key larger than or equalty to searchKey
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::locate(int searchKey, int& eid)
{ 
	int count = getKeyCount();
	int key;
	char* init_buf = buffer + 2*sizeof(int);
	// inital too high? test
	int largest_key;	
	memcpy(&largest_key, init_buf + (count-1)*entry_size, key_size);
	if ( searchKey > largest_key ) {
		return RC_NO_SUCH_RECORD;
	}

	// basic sequential search
	for (int i = 0; i < count; i++) {
		memcpy(&key, init_buf + entry_size*i, key_size);
		if ( key >= searchKey ) {
			eid = i;
			return 0;
		} 
	}
	return RC_NO_SUCH_RECORD; 
}

/*
 * Read the (key, rid) pair from the eid entry.
 * @param eid[IN] the entry number to read the (key, rid) pair from
 * @param key[OUT] the key from the entry
 * @param rid[OUT] the RecordId from the entry
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::readEntry(int eid, int& key, RecordId& rid)
{ 	
	int count = getKeyCount();
	if ( eid > count - 1 ) {
		return RC_FILE_SEEK_FAILED;
	}

	memcpy(&key, buffer + 2*sizeof(int) + entry_size*eid, key_size);
	memcpy(&rid, buffer + 2*sizeof(int) + entry_size*eid + key_size, id_size);
	return 0;
}

/*
 * Return the pid of the next slibling node.
 * @return the PageId of the next sibling node 
 */
PageId BTLeafNode::getNextNodePtr()
{ 
	PageId pid;
	memcpy(&pid, buffer + sizeof(int), sizeof(int));
	return 0; 
}

/*
 * Set the pid of the next slibling node.
 * @param pid[IN] the PageId of the next sibling node 
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::setNextNodePtr(PageId pid)
{ 
	// | 4 = count | 4 = pid | 84 entries
	memcpy(buffer + sizeof(int), &pid, sizeof(int));
	return 0; 
}

/* ********************************************
anatomy of the BUFFER (1024 bytes):
	4 bytes: counter
	pageid pointer (at the very beginning): 4 bytes 
	127 * 8 bytes: tuples (key, pid)
	------ 8 bytes wasted
   ******************************************** */

BTNonLeafNode::BTNonLeafNode() {
	max_num_keys = 127;
	key_size = sizeof(int);
	id_size = sizeof(PageId);
	entry_size = key_size + id_size;
	int init_count = 0;
	memcpy(&buffer, &init_count, sizeof(int));
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.

RC BTNonLeafNode::read(PageId pid, const PageFile& pf)
{ 
	RC rc = pf.read(pid, buffer); 
	return rc;
}
 */
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.

RC BTNonLeafNode::write(PageId pid, PageFile& pf)
{ 
	RC rc = pf.write(pid, buffer); 
	return rc;
}
 */

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node

int BTNonLeafNode::getKeyCount()
{ 	
	int count;
	memcpy(&count, buffer, sizeof(int));
	return count;
}	
 */


/*
 * Insert a (key, pid) pair to the node.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTNonLeafNode::insert(int key, PageId pid)
{ 
	
	// find where to insert
	int count = getKeyCount();

	if ( count == max_num_keys ) { return RC_NODE_FULL; }

	// set up entry (for easier insertion)
	char entry[8];
	memcpy(entry, &key, key_size);
	memcpy(entry + key_size, &pid, id_size);

	// take into account count & first pid & root
	char* init_buf = buffer + 2*sizeof(int);
	
	insert_to_node(init_buf, entry, key, count);

	count++;
	memcpy(buffer, &count, sizeof(int));
	return 0;
}

/*
 * Insert the (key, pid) pair to the node
 * and split the node half and half with sibling.
 * The middle key after the split is returned in midKey.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @param sibling[IN] the sibling node to split with. This node MUST be empty when this function is called.
 * @param midKey[OUT] the key in the middle after the split. This key should be inserted to the parent node.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling, int& midKey)
{
	// create a temp buffer
	char temp_buf[1024];	// holds 128 tuples
	int count = getKeyCount();

	memcpy(temp_buf, buffer + 2*sizeof(int), entry_size*count);

	char entry[8];
	memcpy(entry, &key, key_size);
	memcpy(entry + key_size, &pid, id_size);

	insert_to_node(temp_buf, entry, key, count);
	count++;	// should be +1

	int mid = count/2;
	// original node:
	memcpy(buffer + 2*sizeof(int), temp_buf, entry_size*mid);
	memcpy(buffer, &mid, sizeof(int));	// resetting count

	// new node:
	int new_count = count-mid-1;
	memcpy(sibling.buffer + 2*sizeof(int), temp_buf + entry_size*(mid+1), entry_size*(new_count));
	memcpy(sibling.buffer, &new_count, sizeof(int));	// setting count

	// set up pid1:
	memcpy(sibling.buffer + sizeof(int), temp_buf + entry_size*mid + key_size, id_size);

	memcpy(&midKey, temp_buf + entry_size*mid, key_size);	// return midkey
	return 0; 

}

/*
 * Given the searchKey, find the child-node pointer to follow and
 * output it in pid.
 * @param searchKey[IN] the searchKey that is being looked up.
 * @param pid[OUT] the pointer to the child node to follow.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::locateChildPtr(int searchKey, PageId& pid)
{ 
	// TODO: TEST!!! also maybe include a initial test for high/lows
	// binary search
	int count = getKeyCount();
	int min = 0;
	int max = count - 1;
	int mid;

	char *init_buf = buffer + 2*sizeof(int);	// count + pid1
	int k;

	// inital high
	int largest_key;
	int smallest_key;
	memcpy(&largest_key, init_buf + (count-1)*entry_size, key_size);
	memcpy(&smallest_key, init_buf, key_size);

	if ( searchKey >= largest_key ) {
		//right most pid
		memcpy(&pid, init_buf + (count-1)*entry_size + key_size, id_size);
		return 0;
	} else if ( searchKey < smallest_key) {
		memcpy(&pid, init_buf + key_size, id_size);
		return 0;
	}

	// basic sequential search
	for (int i = 1; i < count; i++) {
		memcpy(&k, init_buf + entry_size*i, key_size);
		if ( searchKey < k ) {
			memcpy(&pid, init_buf + (i-1)*entry_size + key_size, id_size);
			return 0;
		} 
	}

	return RC_NO_SUCH_RECORD; 
}

/*
 * Initialize the root node with (pid1, key, pid2).
 * @param pid1[IN] the first PageId to insert
 * @param key[IN] the key that should be inserted between the two PageIds
 * @param pid2[IN] the PageId to insert behind the key
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::initializeRoot(PageId pid1, int key, PageId pid2)
{
	memcpy(buffer + sizeof(int), &pid1, id_size);
	memcpy(buffer + sizeof(int) + id_size, &key, key_size);
	memcpy(buffer + sizeof(int) + id_size + key_size, &pid2, id_size);
	return 0;
}
